﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTree
{
    /// <summary>
    /// 蛇形遍历，奇数层方向->,偶数层方向<-
    /// </summary>
    class Z_SequenceOrder
    {
        public static int GetDepth(CreatTree.Tree tree,CreatTree.Tree node)
        {
            if (tree == null) return 0;
            if (tree == node) return 1;
            if (tree.Left == node || tree.Right == node) return 2;

            int lDepth = GetDepth(tree.Left, node);
            lDepth = lDepth == 0 ? 0 : lDepth + 1;

            int rDepth = GetDepth(tree.Right, node);
            rDepth = rDepth == 0 ? 0 : rDepth + 1;

            return lDepth >= rDepth ? lDepth : rDepth;
        }

        public static void Z_LevelOrder(CreatTree.Tree tree,Dictionary<int,List<CreatTree.Tree>> dictionary)
        {
            if (tree == null) return;
            Queue<CreatTree.Tree> queue = new Queue<CreatTree.Tree>();
            queue.Enqueue(tree);

            while (queue.Any())
            {
                var item = queue.Dequeue();
                var depth = GetDepth(tree, item);
                List<CreatTree.Tree> list;
                if (!dictionary.TryGetValue(depth,out list))
                {
                    list = new List<CreatTree.Tree>();
                    dictionary.Add(depth, list);
                }
                list.Add(item);

                if (item.Left != null)
                {
                    queue.Enqueue(item.Left);
                }
                if (item.Right != null)
                {
                    queue.Enqueue(item.Right);
                }
            }
        }

        public static void Z_LevelOrder(CreatTree.Tree tree)
        {
            if (tree == null) return;
            Dictionary<int, List<CreatTree.Tree>> dictionary = new Dictionary<int, List<CreatTree.Tree>>();
            Z_LevelOrder(tree, dictionary);

            foreach (KeyValuePair<int,List<CreatTree.Tree>> pair in dictionary)
            {
                if (pair.Key%2 == 0)
                {
                    pair.Value.Reverse();
                }
                pair.Value.ForEach(t => Console.Write(t.Value));
            }
        }
    }
}
